Матч 412, Запрещенные строки (ForbiddenStrings)

Дивизион 1, Уровень 1

Строка, состоящая из букв A, B и C, называется запрещенной, если в ней встречаются три подряд буквы, одна из которых A, другая B, а третья C. Например, строка BAACAACCBAAA является запрещенной, в то время как AABBCCAABB – нет.

Вычислить количество незапрещенных строк длины n.

Класс: ForbiddenStrings

Метод: long countNotForbidden(int n)

Ограничения: 1 £ n £ 30.

Вход. Длина строк n.

Выход. Количество незапрещенных строк длины n.

Пример входа

n

2

3

4

Пример выхода

9

21

51

РЕШЕНИЕ

динамическое программирование

Занесем в rep[i] количество незапрещенных строк длины i, у которых две последние буквы одинаковы. В ячейке nonrep[i] будем хранить число незапрещенных строк длины i, у которых две последние буквы разные. Ответом на задачу будет значение rep[n] + nonrep[n].

Вычислим непосредственно значения ячеек:

rep[1] = 0, rep[2] = 3 (AA, BB, CC),

nonrep[1] = 3 (A, B, C), nonrep[2] = 6 (AB, AC, BA, BC, CA, CB)

Вычисление rep[i]. На место i - ой буквы необходимо ставить ту же букву, которая стоит на (i – 1) - ом месте.

rep[i] = rep[i – 1] + nonrep[i – 1]

Вычисление nonrep[i]. Если (i – 1) - ая и (i – 2) - ая буквы одинаковы, то на i - ое место можно поставить любую из двух букв, не совпадающую с ней. Если (i – 1) - ая и (i – 2) - ая буквы разные, то (i – 1) - ую букву продублировать в качестве i - ой нельзя, нельзя поставить на i - ое место букву, отличную от (i – 1) - ой и (i – 2) - ой. Поэтому в этом случае на i - ое место следует ставить (i – 2) - ую букву.

nonrep[i] = 2 * rep[i – 1] + nonrep[i – 1]

Например, ячейки массивов rep и nonrep будут содержать следующие значения:

i	0	1	2	3	4	5	6	7
rep[i]	0	0	3	9	21	51	123	297
nonrep[i]	0	3	6	12	30	72	174	420

ПРОГРАММА

#include <cstdio>

#include <vector>

using namespace std;

long long rep[31], nonrep[31];

class ForbiddenStrings

{

public:

long long countNotForbidden(int n)

{

int i;

rep[1] = 0; rep[2] = 3;

nonrep[1] = 3; nonrep[2] = 6;

for(i = 3; i <= n; i++)

{

rep[i] = rep[i-1] + nonrep[i-1];

nonrep[i] = 2 * rep[i-1] + nonrep[i-1];

}

return rep[n] + nonrep[n];

}

};